package sorting2;

import java.util.ArrayList;
import java.util.List;

public class BucketSort {

	SelectionSort selectionSort = new SelectionSort();

	@SuppressWarnings({ "unchecked", "rawtypes" })
	public int[] bucketSort(int[] array){
		int maiorNumero = Integer.MIN_VALUE;

		for (int i = 0; i < array.length; i++){
			if (array[i] > maiorNumero){
				maiorNumero = array[i];
			}
		}

		int n = array.length;

		List[] bucket = new ArrayList[(maiorNumero/10)+1];

		for (int i = 0; i < bucket.length; i++){
			bucket[i] = new ArrayList();
		}

		for (int i = 0; i < n; i++){
			bucket[array[i]/10].add(array[i]);
		}

		int[][] arrays = transformaArray(bucket);

		for (int i = 0; i < arrays.length; i++){
			arrays[i] = selectionSort.selectionSort(arrays[i]);
		}
		return concatenaArrays(arrays, n);

	}

	private int[][] transformaArray(@SuppressWarnings("rawtypes") List[] bucket){
		int[][] arrays = new int[bucket.length][];

		for (int i = 0; i < bucket.length; i++){
			arrays[i] = new int[bucket[i].size()];
		}

		for (int i = 0; i < bucket.length; i++){
			for (int j = 0; j < bucket[i].size(); j++){
				arrays[i][j] = (Integer) bucket[i].get(j);
			}
		}
		return arrays;
	}

	private int[] concatenaArrays(int[][] array, int tamanho) {
		int[] retorno = new int[tamanho];
		int cont = 0;

		for (int i = 0; i < array.length; i++){
			for (int j = 0; j < array[i].length; j++){
				retorno[cont] = array[i][j];
				cont ++;
			}
		}
		return retorno;

	}

}